package stack;

import java.util.Deque;
import java.util.LinkedList;

import com.alibaba.fastjson2.JSON;

/**
 * @description: <a href="https://leetcode.cn/problems/trapping-rain-water/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj>42. 接雨水</a>
 * @author: zhaoyinglin
 * @date: 2024/3/6
 */
public class Trap {

    public static void main(String[] args) {
        int[] height = new int[] { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };

        System.out.println(trapV1(height));
        System.out.println(trapV2(height));
        //
        // height = new int[] { 4, 2, 0, 3, 2, 5 };
        //
        // System.out.println(trap(height));

    }

    /**
     * 使用栈
     *
     * @param height
     * @return
     */
    public static int trapV1(int[] height) {
        int area = 0;
        // 不是直接存储值 而是存储下标
        Deque<Integer> stack = new LinkedList<>();

        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.getLast()]) {
                // 移出栈顶元素
                int mid = stack.removeLast();

                if (stack.isEmpty()) {
                    break;
                }

                int leftIndex = stack.getLast();

                int res = (Math.min(height[leftIndex], height[i]) - height[mid]) * (i - leftIndex - 1);

                area += res;

            }
            stack.addLast(i);

        }

        return area;
    }

    /**
     * 使用动态规划
     *
     * @param height
     * @return
     */
    public static int trapV2(int[] height) {

        // dp[i][0] 第i个元素 左边的最大高度 包括当前元素
        // dp[i][1] 第i个元素 右边的最大高度 包括当前元素
        int[][] dp = new int[height.length][2];

        // 第一个元素 左边最大高度为0
        int leftMaxHeight = height[0];
        for (int i = 1; i < height.length; i++) {
            leftMaxHeight = Math.max(leftMaxHeight, height[i]);
            dp[i][0] = leftMaxHeight;
        }

        // 最后一个元素 右边最大高度为0
        int rightMaxHeight = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--) {
            rightMaxHeight = Math.max(rightMaxHeight, height[i]);

            dp[i][1] = rightMaxHeight;
        }

        System.out.println("dp: " + JSON.toJSONString(dp));

        int area = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int h = Math.min(dp[i][0], dp[i][1]);
            if (h <= height[i]) {
                continue;
            }
            area += (h - height[i]);
        }

        return area;
    }

}
